#include <stdio.h>
#include <stdlib.h>
//用链表实现队列

typedef int ElemType;

typedef struct LNode{
    ElemType data;
    struct LNode* next;
}LinkNode;

typedef struct
{
    LinkNode *front;
    LinkNode *rear;
}LinkQueue;

//初始化链表队列
void Queue_init(LinkQueue &LQ)
{
    //申请一个结点空间，作为链表队列的头节点
    LinkNode* node=(LinkNode*)malloc(sizeof(LinkNode));
    if(NULL == node)
    {
        perror("malloc fail\n");
    }
    node->next=NULL;
    LQ.front=LQ.rear=node;
}

//判断是否为空
bool Queue_empty(LinkQueue &LQ)
{
    return LQ.rear == LQ.front;   //
}

//入队列
void enQueue(LinkQueue &LQ,ElemType x)
{
    //为新结点申请一个空间
    LinkNode *node=(LinkNode*)malloc(sizeof(LinkNode));
    if(NULL == node)
    {
        perror("malloc fail\n");
    }
    node->data=x;
    node->next=NULL;
    LQ.rear->next=node;   //链接上新结点
    LQ.rear=node;         //让尾指针指向新的结点
}

//出队列
void deQueue(LinkQueue &LQ,ElemType x)
{
    //判断队列是否为空
    if(Queue_empty(LQ))
    {
        return;
    }
    LinkNode* node=LQ.front->next;  //找到第一个结点
    LQ.front->next=node->next;      //断链
    if(LQ.rear == node)
    {
        LQ.rear=LQ.front;   //如果只有一个结点，那rear指针也将指向头结点
    }
    free(node); //释放删除的结点
    node=NULL;
}

int main() {
    LinkQueue LQ;
    Queue_init(LQ);  //初始化队列

    //入队列
    enQueue(LQ,3);
    enQueue(LQ,4);
    enQueue(LQ,5);
    enQueue(LQ,6);

    ElemType x;
    deQueue(LQ,x);
    deQueue(LQ,x);
    deQueue(LQ,x);
    deQueue(LQ,x);
    deQueue(LQ,x);
    return 0;
}
